#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;

int main()
{
        int n, s;
        cin >> n;
        cin >> s;
        string w;
        vector<int> dis(n + 1, INT32_MAX);
        vector<vector<int>> gh(n + 1, vector<int>(n + 1, 0));
        vector<int> inqueue(n + 1, 0);
        for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                        cin >> w;
                        if(w == "-"){
                                gh[i][j] = INT32_MAX;
                                continue;
                        }else{
                                gh[i][j] = stoi(w);
                        }
                }
        }

        queue<int> q;
        dis[s] = 0;
        q.push(s);
        inqueue[s] = 1;

        while(!q.empty()){
                int u = q.front();
                q.pop();
                inqueue[u] = 0;

                for(int v = 1; v <= n; v++){
                        if(gh[u][v] == INT32_MAX){
                                continue;
                        }
                        if(dis[u] + gh[u][v] < dis[v]){
                                dis[v] = dis[u] + gh[u][v];
                                if(!inqueue[v]){
                                        q.push(v);
                                        inqueue[v] = 1;
                                }
                        }
                }
        }

        for(int v = 1; v <= n; v++){
                if(s == v){
                        continue;
                }
                cout<<"("<<s<<" -> "<<v<<") = "<<dis[v]<<endl;
        }
        return 0;
}